Search for: All records

Motivated by testing for pathogenic diseases we con- sider a new nonadaptive group testing problem for which: (1) positives occur within a burst, capturing the fact that infected test subjects often come in clusters, and (2) that the test outcomes arise from semiquantitative measurements that provide coarse information about the number of positives in any tested group. Our model generalizes prior work on detecting a single burst with classical group testing [1] to the setting of semiquantitative group testing (SQGT) [2]. Speci cally, we study the setting where the burst-length l is known and the semiquantitative tests provide potentially nonuniform estimates on the number of positives in a test group. The estimates represent the index of a quantization bin containing the (exact) total number of positives, for arbitrary thresholds η1,...,ηs. Interestingly, we show that the minimum number of tests needed for burst identi cation is essentially only a function of the largest threshold ηs. In this context, our main result is an order-optimal test scheme that can recover any burst of length l using roughly \ell/2\eta + log (n) measurements. This suggests that 2ηs s+1 a large saturation level ηs is more important than nely quantized information when dealing with bursts. We also provide results for related modeling assumptions and specialized choices of thresholds.